package Tree;

public class BinarySearchTree {

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root ;

    public void insert(int key) {
        if(root == null){
            root = new TreeNode(key);
            return;
        }
        TreeNode treeNode = new TreeNode(key);
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur!=null){
            if(cur.val>key){
                prev = cur;
                cur = cur.left;
            }
            if(cur.val<key){
                prev = cur;
                cur = cur.right;
            }
        }
        if(prev.val>key){
            prev.left = treeNode;
        }else {
            prev.right = treeNode;
        }

    }

    public TreeNode search(int val) {
        TreeNode cur = root;
        if(cur == null){
            return null;
        }
        if(cur.val == val){
            return cur;
        }
        if(root.val<val){
            root = root.right;
            search(val);
        }
        if(root.val>val){
            root = root.left;
            search(val);
        }
        return null;
    }
    public void remove(int val){

    }

}